# 二叉搜索树
# 在二叉搜索树中：
# 1.若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
# 2.若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
# 3.任意结点的左、右子树也分别为二叉搜索树
from collections import deque


class BinTreeNode(object):
    def __init__(self, data):
        self.data = data
        self.left_child = None
        self.right_child = None
        self.parent = None


# 二叉搜索树类
class BST(object):

    def __init__(self, li=None):
        self.root = None
        if li:
            for x in li:
                self.insert_no_recursion(x)

    # 递归调用插入节点
    def insert(self, node, val):
        # 如果节点为空，则将val生成为根节点
        if not node:
            node = BinTreeNode(val)
        elif val < node.data:
            node.left_child = self.insert(node.left_child, val)
            node.left_child.parent = node
        elif val > node.data:
            node.right_child = self.insert(node.right_child, val)
            node.right_child.parent = node
        return node

    # 非递归调用插入节点
    def insert_no_recursion(self, val):
        p = self.root
        # 如果根节点为空，就将当前数据变为根节点
        if not p:
            self.root = BinTreeNode(val)
            return
        while True:
            if val < p.data:
                if p.left_child:
                    p = p.left_child
                else:
                    p.left_child = BinTreeNode(val)
                    p.left_child.parent = p
                    return
            elif val > p.data:
                if p.right_child:
                    p = p.right_child
                else:
                    p.right_child = BinTreeNode(val)
                    p.right_child.parent = p
                    return
            # 如果添加的节点在树中已经存在什么也不做
            else:
                return

    # 查询操作
    def query(self, val):
        p = self.root
        while True:
            if p:
                if p.data > val:
                    p = p.left_child
                elif p.data < val:
                    p = p.right_child
                else:
                    return p
            else:
                return None

    # 情况1：需要删除的节点是叶子节点
    def remove_node_con_1(self, node):
        # 如果是根节点
        if not node.parent:
            self.root = None
        # 如果是左孩子就将父节点的左节点置空
        if node == node.parent.left_child:
            node.parent.left_child = None
        # 如果是右孩子就将父节点的右节点置空
        elif node == node.parent.right_child:
            node.parent.right_child = None

    # 情况2：如果需要删除的节点只有1个左子节点
    def remove_node_con_2_1(self, node):
        # 如果是根节点
        if not node.parent:
            self.root = node.left_child
            node.left_child = None
        # 如果需要删除的节点有的是左节点
        elif node == node.parent.left_child:
            # 父左节点指向左孙
            node.parent.left_child = node.left_child
            # 左孙指向父左节点
            node.left_child.parent = node.parent
        # 如果需要删除的节点是右节点
        else:
            # 父指向右孙
            node.parent.right_child = node.left_child
            # 右孙指向父
            node.left_child.parent = node.parent

    # 情况3：如果需要删除的节点只有1个右子节点
    def remove_node_con_2_2(self, node):
        # 如果是根节点
        if not node.parent:
            self.root = node.right_child
            node.right_child.parent = None
        elif node == node.parent.left_child:
            node.parent.left_child = node.right_child
            node.right_child.parent = node.parent
        elif node == node.parent.right_child:
            node.parent.right_child = node.right_child
            node.right_child.parent = node.parent

    # 搜索二叉树的删除
    def delete(self, val):
        # 不是空树
        if self.root:
            node = self.query(val)
            if not node:
                return False
            # 如果需要删除的值存在于树中
            else:
                # 如果该节点不存在左右孩子节点
                if not node.left_child and not node.right_child:
                    self.remove_node_con_1(node)
                # 如果该节点只有左子节点
                elif node.left_child and not node.right_child:
                    self.remove_node_con_2_1(node)
                # 如果该节点只有右子节点
                elif node.right_child and not node.left_child:
                    self.remove_node_con_2_2(node)
                else:
                    # 两个子节点都存在,找右子树中最小的节点或左子树中最大的节点
                    min_node = node.right_child
                    while min_node.right_child:
                        min_node = min_node.right_child
                    node.data = min_node.data
                    # 删除min_node
                    if min_node.right_child:
                        self.remove_node_con_2_2(min_node)
                    else:
                        self.remove_node_con_1(min_node)

    # 前序遍历 先遍历根节点，再遍历左子树，然后右子树
    def pre_order(self, node):
        if node:
            print(node.data, end=',')
            self.pre_order(node.left_child)
            self.pre_order(node.right_child)

    # 中序遍历 先遍历左子树，再遍历根节点，然后右子树
    def mid_order(self, node):
        if node:
            self.mid_order(node.left_child)
            print(node.data, end=',')
            self.mid_order(node.right_child)

    # 后序遍历 先遍历左子树，再遍历右子树，最后遍历根节点
    def post_order(self, node):
        if node:
            self.post_order(node.left_child)
            self.post_order(node.right_child)
            print(node.data, end=',')

    # 层次遍历
    def level_order(self, node):
        queue = deque()
        queue.append(node)
        # 只要队不空
        while len(queue) > 0:
            n = queue.popleft()
            print(n.data, end=',')
            # 如果左节点存在，入队
            if n.left_child:
                queue.append(n.left_child)
            # 如果右节点存在，入队
            if n.right_child:
                queue.append(n.right_child)


# [4, 5, 6, 11, 2, 3, -1]
tree = BST([4, 5, 6, 11, 2, 3, -1])
# tree.pre_order(tree.root)
# print('')
tree.mid_order(tree.root)
print('')
# tree.post_order(tree.root)
# print('')
# tree.level_order(tree.root)
# print('')
# node = tree.query(12)
# print('value', tree.query(11))
tree.delete(11)
tree.delete(3)
tree.delete(-1)
tree.mid_order(tree.root)
print('')
